// tree.h
// 04/17/2011 : created

#pragma once
#include <vector>
#include "arma_vector.h"

#define for_all_node_data(i) for (int i = 0; i < n(); i++)

class Tree
{
protected:
  typedef std::vector<vec>      dataset_type;
  typedef std::vector<int>      vint_type;
  typedef std::vector<Tree*>    vtree_type;
protected:
  const dataset_type& m_data;
  vint_type& m_idx;
  Tree *m_parent;
  int m_s, m_e;     // [m_s, m_e) interval of indices for this node
  vtree_type m_child;
public:
  Tree(dataset_type& data);
  Tree(Tree* parent, int s, int e);
  virtual ~Tree();

  int n() const { return m_e-m_s; }
  int n_dim() const { return m_data[0].n_elem; }

  int originalIdx(int idx) const { return m_idx[m_s+idx]; }

  const vec& getOriginal(int originalIdx) const { return m_data[originalIdx]; }
  const vec& get(int idx) const { return getOriginal(originalIdx(idx)); }

  void findKNN(const vec& query, std::vector<int>& knnIdx, std::vector<double>& minBound);

  template <typename VISITOR> void visit(VISITOR& v) { v(this); }  // VISITOR implements operator()(KDTree*)
  template <typename VISITOR> void visitRecursive(VISITOR& v) {    // Pre-order visiting
    v(this);
    for (unsigned int i = 0; i < m_child.size(); i++) m_child[i]->visitRecursive(v);
  }
};
